The present invention relates to an algorithm of flash memory and, more particularly, to an algorithm of flash memory capable of quickly building a table and preventing disorder of data due to abnormal disconnection and a control system thereof.
Along with continual progress of the information industry, high-speed data storage devices (memories) play very important roles due to influence of ever faster CPUs and development of information appliance (IA) products. Because flash memories have the characteristics of non-volatility and easily changing access of data, they have been eagerly expected by users.
As shown in FIG. 1A, at least a flash storage device (NAND type flash are the most popular) 11xcx9c19 is connected to a host computer 29 mainly via a control device 20. Of course, the control device 20 can also be built in a subsystem of the host computer 29. The control device 20 comprises a microprocessor 25 therein, which can be connected to the host computer 29 via an interface controller 24 conforming to the protocol of PCMCIA, IDE, ATA, ATAPI, USB, or their combination. One end of the microprocessor 25 can be connected to the data storage device 11 via a storage control logic circuit 26. The microprocessor 25 can also be connected to a buffer controller 22. The buffer controller 22 can temporarily store the data to be accessed by the host computer 29 into a data storage region 21 (a first buffer 211, a second buffer 213, and an N-th buffer 219). Additionally, an ECC logic circuit 23 is respectively connected to the microprocessor 25, the buffer controller 22, and the storage control logic circuit 26. The ECC logic circuit 22 is controlled by the microprocessor 25 to give a corresponding error-correcting code (ECC) data to a data sector to be accessed. Moreover, the microprocessor 25 can be connected to a lookup table 255, which can be used to keep logic block addresses (L0xcx9cLm+1) and all physical block addresses (PBA) of the corresponding data storage device 11.
As shown in FIG. 1B, a memory used by the lookup table 255 such as a random access memory (RAM) mainly uses a word as an access unit, and is partitioned into a plurality of word addresses LBA (logic block address, L0, L1, . . . , Lm, Lm+1, . . . ). Each logical block address includes an address data mapping to a corresponding PBA (physical block address; B3, B2, . . . , Bm, Bm+1, . . . ). The flash memory 11 mainly uses a block as an access unit, and is partitioned into a plurality of physical block addresses B0xcx9cBn. A physical block (Data0xcx9cDatan) of each physical block address includes a plurality of block pages. Each page corresponds to a sector of smallest storage unit at the host end. An error-correcting code (ECC; E0xcx9cEn) field of each corresponding page in a record block and an LBA (L2, L3, L1, . . . , Lm+1) field recording a corresponding logical block address data can be attached behind each physical block. The PBA field of the lookup table 255 corresponds to the LBA field of the memory 11. For example, the logical address data of the data Data0 stored in the physical block B0 of memory points to the LBA L2 in the lookup table 255. Therefore, L2 is recorded in the LBA field thereof (this data will be stored and will not disappear even if disconnection occurs). The PBA field of the sector L2 of the lookup table 255 points to the B0 (this data will disappear after disconnection occurs), as the double arrowheads of the solid line shown in FIG. 1B.
When the system is turned on, the PBA fields of the lookup table 255 do not exist. The microprocessor 25 will scan all physical block addresses and logical block addresses (LBAs) of the flash memories 11xcx9c19, and fill corresponding relations into the physical block address (PBA) fields according to the LBAs, thereby building the complete lookup table 255. However, this way of scanning and then building the lookup table is inconvenient and consumes much operation time.
Moreover, the block B0 is used as a unit when erasing or accessing data due to the structure of the flash memory 11. Therefore, when there exists a physical block to be modified (e.g., the B2), it is necessary to store the data Data2 originally stored in the block B2 into a clean physical block (e.g., Bm+1), record the logical address L1 in the LBA field behind the physical block Bm+1, and then erase the Data2 in the block B2 to be modified so that the block becomes a clean block or is recorded as not in use. However, if an abnormal situation such as a sudden disconnection or a crash occurs when the clean block (e.g., Bm+1) has finished the steps of storing data and filling logical address data but the block B2 to be modified has not yet finished the step of erasing, the host computer will be turned on again and the microprocessor 25 will again scan all physical block addresses of the memory 11. The situation that the two data blocks B2 and Bm+1 are recorded to have the same logical block address L1 and point to the same corresponding address in the lookup table 255 (as the double arrowheads of the dash line shown in FIG. 1B), or the situation that some blocks may be disconnected may occur. Erroneous connection of data or even damage of data may thus easily arise.
Accordingly, the present invention aims to propose an algorithm of flash memory capable of quickly building a lookup table and preventing disorder of data due to abnormal disconnection and a control system thereof.
The primary object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing disorder of data due to abnormal disconnection and a control system thereof, wherein pages of a physical block are utilized to store data of a lookup table. When the system is turned on, quick switching is achieved by directly storing into a buffer from the block pages without a microprocessor utilizing a scan program to perform scan of logical addresses to all physical blocks of each memory. Therefore, the operation of the microprocessor can be simplified, and the operation time can also be greatly saved.
The secondary object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, wherein pages of physical blocks of the memory can store data of a lookup table, thereby preventing abnormality of data due to improper operation.
Another object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, wherein data of a lookup table can be protected by a set of ECC data to enhance the accuracy of data.
Yet another object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, wherein all memory blocks can be partitioned into a plurality of segments according to capacity of memory of buffers or block pages. Each segment has a corresponding mapping table of buffers to build the mapping relations of data. When there are data of a block modified, only the related data of the mapping table will be affected. Therefore, time of modification of the mapping table can be effectively decreased, and the situation of erroneous connection of data can be effectively reduced.
Still yet another object of the present invention is to provide an algorithm of flash memory capable of quickly building a lookup table and preventing improper operation and a control system thereof, whereby all physical blocks can be partitioned into a plurality of segments to let the size of a mapping table be reduced to be just a sector (256 words) so that the mapping table can be used as general data and stored into the flash memory. Therefore, the capacity of memory for recording data of physical block addresses can be greatly saved. The present invention can also apply to a storage system connecting a plurality of flash memories.
The various objects and advantages of the present invention will be more readily understood from the following detailed description when read in conjunction with the appended drawing, in which: